public class Solution {
    public static List<List<Integer> > fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        Set<List<Integer> > sets = new HashSet<>();
        for(int k = 0; k < nums.length - 3; k++) {
            int s = target - nums[k];
            for(int i = k + 1; i < nums.length - 2; i++) {
                int start = i + 1;
                int end = nums.length - 1;
                while(start < end) {
                    int t = nums[start] + nums[end];
                    if(t > s - nums[i]) {
                        end--;
                    } else if(t < s - nums[i]) {
                        start++;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[k]);
                        list.add(nums[i]);
                        list.add(nums[start]);
                        list.add(nums[end]);
                        sets.add(list);
                        while(start < nums.length - 1 && nums[start + 1] == nums[start]) {
                            start++;
                        }
                        while(end > 0 && nums[end - 1] == nums[end]) {
                            end--;
                        }
                        start++;
                        end--;
                    }
                }
            }
        }
        
        return new ArrayList<>(sets);
    }
}
